package lcr;

public class Test0106 {
    public static void main(String[] args) {
        new Solution0106_1().isBipartite(new int[][]{{1,2,3},{0,2},{0,1,3},{0,2}});
    }
}

class Solution0106_1 {
    int[][] graph;
    public boolean isBipartite(int[][] graph) {
        this.graph=graph;
        int length = graph.length;
        int[] color = new int[length];
        for (int i = 0; i < length; i++)
            if (color[i]==0) if(!dfs(i,1,color)) return false;

        return true;
    }

    public boolean dfs(int cur,int c,int[] color){
        int nextC = c == 1 ? 2 : 1;
        if (color[cur]==0) {
            color[cur]=c;
            for (int num : graph[cur]){
                if(!dfs(num,nextC,color)) return false;
            }
        }else return color[cur] == c;

        return true;
    }
}
